#pragma once

#include <vector>
#include <utility>

namespace sorting
{
    /**
     * @brief       冒泡排序
     * @note        增加了标志优化
     * @tparam  T   基本数据类型
     * @param   vec 基本数据类型的数组
     */
    template <typename T>
    void BubbleSort(std::vector<T> &vec)
    {
        using std::size_t;

        const size_t len = vec.size();
        if (len <= 1)
        {
            return;
        }

        bool flag = true;
        for (size_t i = 0; flag && i < len - 1; ++i)
        {
            flag = false;
            for (size_t j = 0; j < len - i - 1; ++j)
            {
                if (vec[j + 1] < vec[j])
                {
                    std::swap(vec[j], vec[j + 1]);
                    flag = true;
                }
            }
        }
    }

    /**
     * @brief       双向冒泡排序
     * @note        增加了标志优化
     * @tparam  T   基本数据类型
     * @param   vec 基本数据类型的数组
     */
    template <typename T>
    void CocktailSort(std::vector<T> &vec)
    {
        using std::size_t;

        const size_t len = vec.size();
        if (len <= 1)
        {
            return;
        }

        bool flag = true;
        size_t left = 0, right = len - 1;

        while (flag)
        {
            flag = false;

            // 从左到右扫描，将最大值置于最右侧
            for (size_t i = left; i < right; ++i)
            {
                if (vec[i] > vec[i + 1])
                {
                    std::swap(vec[i], vec[i + 1]);

                    flag = true;
                }
            }
            right--; // 右边界左移，因为最右边已经是最大的元素

            // 如果发现没有交换，可以提前终止排序
            if (!flag)
            {
                break;
            }

            // 再次重置标志
            flag = false;

            // 从右到左扫描，把最小值置于最左侧
            for (size_t j = right; j > left; --j)
            {
                if (vec[j] < vec[j - 1])
                {
                    std::swap(vec[j - 1], vec[j]);
                    flag = true;
                }
            }
            left++; // 左边界右移，因为最左边已经是最小的元素
        }
    }
} // namespace sorting